import heapq

def solve(nums):
    n = len(nums)
    k = n // 2
    # 如果不需要拿任何盲盒，则返回0
    if k == 0:
        return 0
    # 使用数组模拟双向链表
    # left[i] 和 right[i] 分别是索引 i 的左右邻居的索引
    left = [i - 1 for i in range(n)]
    right = [i + 1 for i in range(n)]
    right[n - 1] = -1  # -1 代表链表末端
    # 标记一个元素是否仍然有效（未被选择或作为邻居被移除）
    active = [True] * n
    # Python的heapq是最小堆，所以我们存入负值来模拟最大堆
    # 堆中存放元组 (-价值, 索引)
    pq = [(-nums[i], i) for i in range(n)]
    heapq.heapify(pq)

    total_value = 0
    # 执行 k 次选择
    for _ in range(k):
        # 找到当前有效的最大值
        while not active[pq[0][1]]:
            heapq.heappop(pq)

        neg_val, i = heapq.heappop(pq)
        val = -neg_val

        total_value += val
        # 将当前节点及其邻居从链表中移除，并用一个新节点代替
        l_idx, r_idx = left[i], right[i]
        # 将当前节点和左右邻居标记为失效
        active[i] = False
        if l_idx != -1:
            active[l_idx] = False
        if r_idx != -1:
            active[r_idx] = False
        # 计算新节点的价值
        left_val = nums[l_idx] if l_idx != -1 else 0
        right_val = nums[r_idx] if r_idx != -1 else 0
        new_val = left_val + right_val - val

        # 将当前节点 i "复用"为合并后的新节点
        nums[i] = new_val
        heapq.heappush(pq, (-new_val, i))

        # 更新链表指针，将新节点连接到外侧邻居
        new_l_idx = left[l_idx] if l_idx != -1 else -1
        new_r_idx = right[r_idx] if r_idx != -1 else -1

        # 连接左边
        if new_l_idx != -1:
            right[new_l_idx] = i
        left[i] = new_l_idx
        # 连接右边
        if new_r_idx != -1:
            left[new_r_idx] = i
        right[i] = new_r_idx

    return total_value
# --- 示例测试 ---
# 示例 1
input1 = [-1, 2, 0, -1, 1]
output1 = solve(input1)
print(f"输入: {input1}")
print(f"输出: {output1}")  # 预期输出: 3

# 示例 2
input2 = [1, 2, 3, 4, 5]
output2 = solve(input2)
print(f"输入: {input2}")
print(f"输出: {output2}")  # 预期输出: 8 (3+5)

